package com.leetcode.demo;

import java.util.Stack;

/**
 * @author 王溪源
 * @ClassName: Question20
 * @Description: 给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。
 * 输入：s = "([)]"
 * 输出：false
 * 输入：s = "{[]}"
 * 输出：true
 * @Date 2021/8/22 23:32
 **/
public class Question20 {
    public boolean isValid(String s) {
        if (s.length () % 2 != 0) {
            return false;
        }
        StringBuilder sb = new StringBuilder (s);
        for (int i = 0; i < sb.length () / 2; i++) {
            // 如果括号不是紧紧相拥，那中间肯定会先嵌套 此处if是后面修改逻辑
            if (s.charAt (i) == getMatchedCharacter (s.charAt (i + 1))) {
                return isValid (sb.delete (i,i+2).toString ());
            }
            // 括号都是成对出现的，而且字符串长度必须是偶数，左括号下标索引+右括号下标索引的值应该等于字符串长度-1
//            if (i < s.length () / 2 && s.charAt (i) != getMatchedCharacter (s.charAt (s.length () - 1 - i))) {
//                return false;
//            }
        }
        return true;
    }

    public char getMatchedCharacter(char c) {
        switch (c) {
            case ')':
                return '(';
            case '}':
                return '{';
            case ']':
                return '[';
            default:
                return 'N';
        }
    }

    public boolean isValid2(String s){
        if (s.length () % 2 != 0) {
            return false;
        }
        Stack<Character> stack = new Stack<> ();
        for (int i = 0; i < s.length (); i++) {
            switch (s.charAt (i)){
                case '{':
                    stack.push ('}');
                    break;
                case '[':
                    stack.push (']');
                    break;
                case '(':
                    stack.push (')');
                    break;
                default:
                    if(!stack.isEmpty () && s.charAt (i) != stack.pop ()){
                        return false;
                    }
            }
        }
        return stack.empty ();
    }

    public boolean isValid3(String s){
        if (s.length () % 2 != 0) {
            return false;
        }
        for (int i = 0; i < s.length () / 2; i++) {
            s = s.replace ("{}","").replace ("[]","")
                    .replace ("()","");
        }
        return s.isEmpty ();
    }

    public static void main(String[] args) {
        Question20 question20 = new Question20 ();
        System.out.println (question20.isValid2 ("{[]}"));
        System.out.println (question20.isValid2 ("()"));
        System.out.println (question20.isValid2 ("([)]"));
        // 上面的解题思路，当出现这个情况会是false，需要修改逻辑
        System.out.println (question20.isValid2 ("()[]{}"));
        System.out.println (question20.isValid2 ("(){}}{"));
        System.out.println (question20.isValid2("(([]){})"));
    }
}
